题目来源:洛谷P2678 跳石头
这是一道标准的 “最大值最小”或“最小值最大“ 的题,遇到这种题,我们就可以使用 贪心+二分查找 的方法来做
二分答案/二分查找
有序(单调)的,有界的就可以用二分法查找。
有界:对于本题,我们可以发现,这个所谓的最短跳跃距离显然不能超过一个范围(跳一次从头跳到尾)。也就是说,答案是有一个确定的范围限制的(开头到结尾的距离内),我们就可以考虑一种另外的方法去解决——枚举答案,并去验证答案是否可行,这实际上是一种倒推
二分:那么如何确保我们可以最快的找到答案呢?二分是最好选择
单调:二分的前提条件是什么?是答案区间是整体有序的。我们只考虑合法解,并称之为可行解。考虑所有可行解,我们肯定是要从这些可行解中找到一个最好的作为我们的答案, 这个答案我们称之为最优解。最优解一定可行,但可行解不一定最优。
总结来说,可以使用二分查找的条件:解的上下界确定(l=0,r=L),可以写出判断条件(f(x)<=m),解具有区间单调性(在某个值之前条件都成立,之后都不成立)
本题和 P2855 River Hopscotch 是同一道题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int rocks[50003],ending,num,removed,result; void finding(int,int); int main() { cin>>ending>>num>>removed; for(int i=1;i<=num;i++) cin>>rocks[i]; rocks[0]=0; rocks[num+1]=ending; sort(rocks+1,rocks+num+1);
finding(0,ending); cout<<result; return 0; } void finding(int m, int n) { int mid=(m+n)/2, removing=0; int now=0,pointer=0; while(pointer<num){ pointer++; if(rocks[pointer]-rocks[now]<mid) removing++; else now=pointer; } if(m<=n){ if(removing>removed) finding(m,mid-1); else if(removing<=removed) { result=mid; finding(mid+1,n);} } }
|
二分查找模板
非递归形式的二分查找模板
1 2 3 4 5 6 7 8 9 10 11 12
| int l=1,r=ll; while(l<=r) { int mid=(l+r)>>1,q=check(mid); if(check) { ll=mid+1; ans=mid; } else l=mid+1; }
|
下面是一个二分查找的样例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int stall[100005],cow_num,stall_num,ans; void finding(int,int); int main() { cin>>stall_num>>cow_num; for(int i=1;i<=stall_num;i++) cin>>stall[i]; sort(stall+1,stall+stall_num+1);
finding(1,stall[stall_num]);
cout<<ans; return 0; } void finding(int m, int n) { int mid=(m+n)/2,now=1,pointer=1,cow_mid=1; while(pointer<stall_num){ pointer++; if(stall[pointer]-stall[now]>=mid){ cow_mid++; now=pointer;} }
if(m<=n){ if(cow_mid>=cow_num) {ans=mid; finding(mid+1,n);} else finding(m,mid-1); } }
|